/**
 * 
 */
package string.passed;

import java.util.ArrayList;

/**
 * @author xyyi
 *
 */
public class GenerateParentheses {

	/**
	 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
	
	For example, given n = 3, a solution set is:
	
	"((()))", "(()())", "(())()", "()(())", "()()()"
	 */
	public ArrayList<String> generateParenthesis(int n) {
		// Start typing your Java solution below
		// DO NOT write main() function

		ArrayList<String> list = new ArrayList<String>();
		generateParenthesis(n, n, list, new StringBuilder());
		//generateParenthesis(0, 0, 0, n, list, new StringBuilder());
		return list;
	}

	private void generateParenthesis(int left, int right,
			ArrayList<String> list, StringBuilder s) {
		if (left == 0 && right == 0) {
			list.add(s.toString());
		} else {
			if (left > 0) {
				s.append('(');
				generateParenthesis(left - 1, right, list, s);
				s.setLength(s.length() - 1);
			}
			if (right > left) {
				s.append(')');
				generateParenthesis(left, right - 1, list, s);
				s.setLength(s.length() - 1);
			}
		}

	}

	private void generateParenthesis(int index, int left, int right, int n,
			ArrayList<String> list, StringBuilder s) {
		// Start typing your Java solution below
		// DO NOT write main() function
		if (index == 2 * n) {
			list.add(s.toString());
		} else {
			if (left < n) {
				s.append('(');
				generateParenthesis(index + 1, left + 1, right, n, list, s);
				s.setLength(s.length() - 1);
			}

			if (right < left) {
				s.append(')');
				generateParenthesis(index + 1, left, right + 1, n, list, s);
				s.setLength(s.length() - 1);
			}
		}
	}

	/**
	 * 
	 */
	public GenerateParentheses() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 3;
		GenerateParentheses gp = new GenerateParentheses();
		ArrayList<String> list = gp.generateParenthesis(n);
		for (String s : list) {
			System.out.println(s);
		}

	}

}
